Теорема Оре

Пусть $G$ — обыкновенный граф с $n$ вершинами, $n > 2$. Если $\deg(u) + \deg(v) \ge n$ для любых двух несмежных вершин $u$ и $v$ графа $G$, то граф $G$ гамильтонов.

От противного. Пусть существует граф $G$, удовлетворяющий всем условиям теоремы и не являющийся гамильтоновым. Если возможно, будем добавлять к $G$ новые ребра так, чтобы граф оставался негамильтоновым. Новый граф тоже будет удовлетворять всем условиям теоремы. В какой-то момент мы получим граф $G'$, который удовлетворяет всем условиям теоремы и является **максимальным** негамильтоновым, т.е. он превращается в гамильтонов при добавлении любого ребра. Существование такого $G'$ следует из того, что полный граф гамильтонов. Получим противоречие, построив гамильтонов цикл в $G'$. Пусть $u$ и $v$ — произвольные несмежные вершины графа $G'$. В $G'$ нет гамильтонова цикла, но при добавлении ребра $(u,v)$ он появится. Следовательно, в $G'$ есть гамильтонов $(u,v)$-путь: $v_1, v_2, \ldots, v_n$, где $v_1 = u$ и $v_n = v$. Пусть $S = \{i \mid u \text{ смежна с } v_{i+1}\}$ и $T = \{i \mid v \text{ смежна с } v_i\}$. Тогда $|S| = \deg(u)$ и $|T| = \deg(v)$. По условию теоремы $|S| + |T| \ge n$. Элементы множеств $S$ и $T$ являются числами от $1$ до $n-1$. Из этого следует, что $S \cap T \neq \varnothing$. Пусть $i \in S \cap T$. Тогда в $G'$ есть ребра $(u, v_{i+1})$ и $(v_i, v)$. Следовательно, в графе $G'$ есть гамильтонов цикл: $u \to v_2 \to \ldots \to v_i \to v \to v_{n-1} \to \ldots \to v_{i+1} \to u$. Требуемое противоречие получено. $\square$